Subset Sum

Statement#

Given a set of positive numbers arr and a value total, determine if there exists a subset in the given set whose sum is equal to total. A subset can be an empty set, or it can either consist of some elements of the set or all the elements of the set.

Let’s say you are given a set = {1, 2, 3, 7} and a total = 6. The output will be TRUE as the subset = {1, 2, 3} adds up to make the desired total (1+2+3) = 6.

Constraints:

• $1\leq$ arr.length $\leq 900$
• $0\leq$ total $\leq 10^5$
• $1\leq$ arr[i] $\leq 10^4$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using 0/1 Knapsack dynamic programming pattern.

Naive approach#

The naive approach is to find all the possible combinations from the set, which makes our total. As we know, we are to trace down a subset and we can not repeat any element from the set. Therefore, every element in arr is considered only once.

For example, we have the following arr of positive values

• arr: {3, 5, 8, 10}

and total = $13$. We return TRUE as the following two subsets sum up to the required total.

• {$5, 8$} such that $5+8 = 13$
• {$10, 3$} such that $10+3 = 13$

The recursive solution will be to check every element of the arr:

• If it does not contribute to making up the total, we ignore that number and proceed with the rest of the elements, i.e., subset_sum_rec(arr, n-1, total).

OR

• If it does contribute to making up the total, we subtract the total from the current number and proceed with the rest of the elements till the given total is zero, i.e., subset_sum_rec(arr, n-1, total-arr[n-1]).

Let’s try to implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^n)$, where $n$ is the total number of elements. This is because we have two possible choices every time, either to include the element or not.

Space complexity#

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table.

As we have to check every possible combination of all elements in the arr , we can store computed values and use them later on whenever we need them. For this purpose, we will use a 2-D table dp that will store the computed results at each step. Whenever we encounter a subproblem whose value is already calculated, we will simply look up from the table instead of recalculating it. The last index of dp will contain the required output.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 2-D table, the time complexity of this approach is reduced to $O(n * m)$, where $n$ is the number of items and $m$ is the total sum we need to achieve.

Space complexity#

We now need $O(n * m)$ space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. A 2-D table of size [n + 1] * [total + 1] is used here. We will solve this problem by first solving the sub-problems and eventually solving the problem.

We will initialize the table so that the rows will represent the possible subsets, and the columns will show the total we need to achieve. At any given time, each column represents the amount that we have to calculate using the elements of the given set at the respective row. Now, there will be a check for each element as to whether it will contribute to making up the total or not.

Let’s look at the following illustration to get a better understanding of the solution:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we have to populate a 2-D table to store the results of sub-problems, therefore, the time complexity of this approach will also be $O(n * m)$, where $n$ is the number of items and $m$ is the total sum we need to achieve.

Space complexity#

We need $O(n * m)$ space in memory to store the intermediate values.